package cn.fxzhang.leetcode.no00;

/**
 * 74. 搜索二维矩阵
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 *  1 <= m, n <= 100
 *  -10^4 <= matrix[i][j], target <= 10^4
 *
 * 类型：数组/二分查找
 * 题解：根据有序性，可以用枚举或者二分
 * 时间复杂度：O(lg(NM))
 * 空间复杂度：O(1)
 *
 * 提交记录(1/1)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 37.8 MB, 击败了77.84%
 *
 * 【中等】通过次数116,961提交次数267,848
 * @author 张晓帆
 * @date 2021/3/30
 */
public class P0074_Search_A_2d_Matrix {

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int minRow = 0;
        int maxRow = m-1;
        while (minRow <= maxRow){
            int midRow = (minRow + maxRow) >> 1;
            if (target >= matrix[midRow][0]){
                minRow = midRow + 1;
            } else {
                maxRow = midRow - 1;
            }
        }
        int targetRow = Math.max(minRow - 1, 0);

        int minCol = 0;
        int maxCol = n -1;
        while (minCol <= maxCol) {
            int midCol = (minCol + maxCol) >> 1;
            if (target == matrix[targetRow][midCol]){
                return true;
            }
            if (target > matrix[targetRow][midCol]){
                minCol = midCol + 1;
            } else {
                maxCol = midCol - 1;
            }
        }
        return false;
    }
}
